BZOJ2141 排队 <分块+树状数组>

Problem

排队

Description

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。
红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。
设第个小朋友的身高为，我们定义一个序列的杂乱程度为满足且的数量。
幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。
为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

Input

第一行为一个正整数，表示小朋友的数量。
第二行包含个由空格分隔的正整数，依次表示初始队列中小朋友的身高。
第三行为一个正整数，表示交换操作的次数。
以下行每行包含两个正整数和，表示交换位置与位置的小朋友。

Output

输出文件共行，第行一个正整数表示交换操作结束后，序列的杂乱程度。

Sample Input

3
130 150 140
2
2 3
1 3

Sample Output

1
2
3

1
0
3

Hint

样例说明
未进行任何操作时，满足条件；
操作结束后，序列为，不存在满足条件的；
操作结束后，序列为，有,,共对满足条件的
数据规模
，，，，。

标签：分块 树状数组

Solution

分块基础应用之带交换逆序对。

将原序列分为个大小为的块，每块内维护一个值域树状数组，记录每个值的个数。
一开始增量计算总逆序对对数，随后对每个操作计算会增加/减少多少对逆序对。
当交换时，对于，

若，则
若，则
若，则
若，则

整块直接用树状数组统计，剩余部分暴力即可。

Code

#include <bits/stdc++.h>
#define MAX_N 20000
#define MAGIC ((int)sqrt(n))
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, cnt, tot, a[MAX_N+5], b[MAX_N+5];
int BIT[150][MAX_N+5]; map <int, int> h;
int id(int p) {return (p-1)/MAGIC+1;}
void inc(int tr[], int p) {for (; p <= n; p += (p&-p)) tr[p]++;}
void dec(int tr[], int p) {for (; p <= n; p += (p&-p)) tr[p]--;}
int sum(int tr[], int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i]; sort(b+1, b+n+1);
    for (int i = 1; i <= n; i++) if (!i || (b[i]^b[i-1])) h[b[i]] = ++cnt;
    for (int i = 1; i <= n; i++) inc(BIT[0], a[i] = h[a[i]]), tot += i-sum(BIT[0], a[i]);
    for (int i = 1; i <= n; i++) inc(BIT[id(i)], a[i]); printf("%d\n", tot); read(m);
    while (m--) {
        int x, y; read(x), read(y); if (x > y) swap(x, y);
        if (id(x) < id(y)) {
            for (int i = id(x)+1; i <= id(y)-1; i++)
                tot -= sum(BIT[i], a[x]-1), tot += sum(BIT[i], n)-sum(BIT[i], a[x]), 
                tot += sum(BIT[i], a[y]-1), tot -= sum(BIT[i], n)-sum(BIT[i], a[y]);
            for (int i = x+1; i <= id(x)*MAGIC; i++)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
            for (int i = y-1; i >= (id(y)-1)*MAGIC+1; i--)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
        } else
            for (int i = x+1; i <= y-1; i++)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
        tot += (a[x] < a[y]), tot -= (a[x] > a[y]);
        dec(BIT[id(x)], a[x]), dec(BIT[id(y)], a[y]);
        inc(BIT[id(x)], a[y]), inc(BIT[id(y)], a[x]);
        swap(a[x], a[y]), printf("%d\n", tot);
    }
    return 0;
}